1. Field of the Invention
The present invention relates to an error correction decoding field, and more particularly, to a Reed-Solomon (RS) decoder having a new polynomial arrangement architecture for realizing a modified Euclidean algorithm and a decoding method therefor.
2. Description of the Related Art
A RS decoder is generally used for correcting errors generated during transmission in a digital communication system using a high definition television (HDTV), a digital versatile disc (DVD), or a compact disc (CD). Although, the RS decoder has excellent error correcting capability, it has a very complicated architecture. In general, an RS code is expressed as RS(N,I). One packet of information is constructed of N symbols. Among these symbols, I symbols show a message and the rest N-I symbols show a parity. Each symbol is comprised of m bits.
FIG. 1 is a block diagram of a conventional RS decoder using a modified Euclidean algorithm, which is disclosed in "On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays", H. M. Shao and I. S. Reed, IEEE Trans. Comput, vol. 37, October 1988, pp. 1273-1280.
In FIG. 1, the root .alpha..sup.-i of an initial error locator polynomial calculated by input erasure location information is input to first and second polynomial expanders 106 and 108. An erasure indicates an error, the location of which is known from the received data.
The initial error locator polynomial .GAMMA.(x) expanded by the first polynomial expander 106 can be represented by Equation 1. A modified syndrome polynomial T(x) which is a key equation expanded by the second polynomial expander 108 can be represented by Equation 2. ##EQU1##
wherein, .PI. represents a multiplication. The root of the initial error locator polynomial .GAMMA.(x) shows the location where an error is generated. Namely, if .alpha..sup.-i is the root, the error is generated in the (i+1)th code word among received code words. In the (i+1)th code word, the code index corresponds to i. EQU T(x)=S(x).GAMMA.(x) mod x.sup.2t [EQUATION 2]
wherein, T(x), S(x), and t respectively represent a modified syndrome polynomial, a syndrome polynomial, and the number of being capable of correcting errors.
When the calculation of the initial error locator polynomial and the modified syndrome polynomial is completed, an error evaluator polynomial .omega.(x) and an error locator polynomial .sigma.(x) are extracted by a modified Euclidean algorithm calculator 110 using the modified Euclidean algorithm.
When the iterative equations represented in Equations 4 through 7 are iterated 2t times, the desired error evaluator polynomial .omega.(x) and error locator polynomial .sigma.(x) are obtained as a result by the modified Euclidean algorithm calculator 110. These are called the modified Euclidean algorithm, which is provided in the above document by H. M. Shao and I. S. Reed. EQU .mu..sub.0 (x)=.GAMMA.(x),R.sub.0 (x)=x.sup.2t,.lambda..sub.0 (x)=0,Q.sub.0 (x)=T(x) [EQUATION 3] EQU R.sub.i (x)=[.sigma..sub.i-1 b.sub.i-1 R.sub.i-1 (x)+.sigma..sub.i-1 +L a.sub.i-1 Q.sub.i-1 (x)]-x.sup..vertline.l.sup..sub.i-1 .sup..vertline. [.sigma..sub.i-1 a.sub.i-1 Q.sub.i-1 (x)+.sigma..sub.i-1 b.sub.i-1 R.sub.i-1 (x)] [EQUATION 4] EQU .lambda..sub.i (x)=[.sigma..sub.i-1 b.sub.i-1.lambda..sub.i-1 (x)+.sigma..sub.i-1 +L a.sub.i-1.mu..sub.i-1 (x)]-x.sup..vertline.l.sup..sub.i-1 .sup..vertline. [.sigma..sub.i-1 a.sub.i-1.mu..sub.i-1 (x)+.sigma..sub.i-1 b.sub.i-1.lambda..sub.i-1 (x)] [EQUATION 5] EQU Q.sub.i (x)=.sigma..sub.i-1 Q.sub.i-1 (x)+.sigma..sub.i-1 +L R.sub.i-1 (x) [EQUATION 6] EQU .mu..sub.i (x)=.sigma..sub.i-1.mu..sub.i-1 (x)+.sigma..sub.i-1 +L .lambda..sub.i-1 (x) [EQUATION 7]
wherein a.sub.i-1 and b.sub.i-1 are respectively the coefficients of the highest degree terms of R.sub.i-1(x) and Q.sub.i-1(x). EQU l.sub.i-1 =deg(R.sub.i-1 (x))-deg(Q.sub.i-1 (x)) [EQUATION 8]
##EQU2##
Namely, as shown in Equations 8 and 9, when the degree of R.sub.i-1(x) is equal to or larger than that of Q.sub.i-1(x), .sigma..sub.i-1 has a value of "1". If not, .sigma..sub.i-1 has a value of "0".
When the condition shown in the following Equation 10 is satisfied, the above iterative equations (Equations 4 through 7) are terminated. EQU deg(.lambda..sub.i (x))&gt;deg(R.sub.i (x)) [EQUATION 10]
When the above iterative equations (Equations 4 through 7) are completed, the error locator polynomial .sigma.(x) and the error evaluator polynomial .omega.(x) are obtained as shown in the equations 11 and 12. EQU .sigma.(X)=.lambda..sub.i (x) [EQUATION 11] EQU .omega.(x)=R.sub.i (x) [EQUATION 12]
The initial values of the four polynomials R.sub.i (x), Q.sub.i (x), .lambda..sub.i (x), and .mu..sub.i (x) are represented in the above Equation 3. The error locator polynomial .sigma.(x) and the error evaluator polynomial .omega.(x) can be obtained without repeating the iterative equations (Equations 4 through 7) 2t times, under the condition that the degree of .lambda..sub.i (x) is larger than that of R.sub.i (x). .lambda..sub.i (x) becomes the error locator polynomial and R.sub.i (x) becomes the error estimator polynomial.
A conventional polynomial arrangement architecture for realizing the modified Euclidean algorithm is represented in FIG. 2. In the polynomial arrangement shown in FIG. 2, the polynomials R(x) and Q(x), the degrees of which decrease as an iterative operation process proceeds, are arranged in registers 132 and 134 loaded in the modified Euclidean algorithm calculator 110 from the right side. The polynomials .lambda.(x) and .mu.(x), the degrees of which increase as an iterative operation process proceeds, are arranged in registers 136 and 138 from the left side. In this case, the degrees of the respective polynomials must be stored in an additional memory (not shown) for generating a control signal required for iterative calculations.
The conventional polynomial arrangement architecture for realizing the modified Euclidean algorithm has problems in that the degrees of the respective polynomials must always be stored in the additional memory, and as many as log.sub.2 2t subtracters are required since the degrees must be compared as shown in Equation 8 for generating the control signal required for performing the above Equation 9. Further, the degrees must be buffered when the polynomials are buffered since the degrees of the polynomials will be used in subsequent iterative operations.